/*
 * @Author: wwssaabb
 * @Date: 2021-11-26 09:06:43
 * @LastEditTime: 2021-11-26 09:24:38
 * @FilePath: \handwritten-code\algorithm\有效括号.js
 */

/* 
给定一个只包括 '('，
')'，
'{'，
'}'，
'['，
']'
的字符串 s， 判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入： s = "()"
输出： true
示例 2：

输入： s = "()[]{}"
输出： true
示例 3：

输入： s = "(]"
输出： false
示例 4：

输入： s = "([)]"
输出： false
示例 5：

输入： s = "{[]}"
输出： true

来源： 力扣（ LeetCode）
链接： https: //leetcode-cn.com/problems/valid-parentheses
*/

//模拟栈
var isValid = function (s) {
  let len = s.length
  if (len % 2 === 1) return false
  let map = new Map([
    [')', '('],
    ['}', '{'],
    [']', '[']
  ])
  let tak = []
  for (const ch of s) {
    if (map.has(ch)) {
      if (!tak.length || map.get(ch) !== tak[tak.length - 1]) return false
      tak.pop()
    } else {
      tak.push(ch)
    }
  }
  return !tak.length
}

console.log(isValid('()')) //true
console.log(isValid('()[]{}')) //true
console.log(isValid('(]')) //false
console.log(isValid('([)]')) //false
console.log(isValid('{[]}')) //true

//解题思路
/* 
  由于是偶数的集合，所以s的长度必须是一个偶数
  遍历字符串， 遇到开始符号, 例如(、{、[时进栈，push
    遇到结束符号出栈， 例如)、}、]时出栈
    出栈时和顶栈的符号不是同一类型则返回，同一类型则出栈pop
*/